{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's make up a matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n=5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5×5 Array{Float64,2}:\n",
       " 3.0      21.0   8.0  19.0       6.0    \n",
       " 5.0      -4.0  11.0  14.0      13.0    \n",
       " 2.23607  -2.0   2.5   0.0       0.0    \n",
       " 0.0       0.0   0.0   0.0       1.0    \n",
       " 2.0      99.0   5.0   3.14159   3.14159"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = [ 3 21 8 19 6\n",
    "    5 -4 11 14 13\n",
    "     √5 -2 2.5 0 0\n",
    "      0 0 0 0 1\n",
    "     2 99 5 π π]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4-element Array{Float64,1}:\n",
       " 1.66667 \n",
       " 0.745356\n",
       " 0.0     \n",
       " 0.666667"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m1 = A[2:5,1] / A[1,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4-element Array{Float64,1}:\n",
       " -1.66667 \n",
       " -0.745356\n",
       " -0.0     \n",
       " -0.666667"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E1 = eye(5)\n",
    "E1[2:5,1] = -m1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5×5 Array{Float64,2}:\n",
       " 3.0   21.0      8.0        19.0       6.0     \n",
       " 0.0  -39.0     -2.33333   -17.6667    3.0     \n",
       " 0.0  -17.6525  -3.46285   -14.1618   -4.47214 \n",
       " 0.0    0.0      0.0         0.0       1.0     \n",
       " 0.0   85.0     -0.333333   -9.52507  -0.858407"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A2 = E1 * A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Array{Float64,1}:\n",
       "  0.452628\n",
       " -0.0     \n",
       " -2.17949 "
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m2 = A2[3:5,2]/A2[2,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Array{Float64,1}:\n",
       " -0.452628\n",
       "  0.0     \n",
       "  2.17949 "
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E2 = eye(5)\n",
    "E2[3:5,2]= -m2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5×5 Array{Float64,2}:\n",
       " 1.0   0.0       0.0  0.0  0.0\n",
       " 0.0   1.0       0.0  0.0  0.0\n",
       " 0.0  -0.452628  1.0  0.0  0.0\n",
       " 0.0   0.0       0.0  1.0  0.0\n",
       " 0.0   2.17949   0.0  0.0  1.0"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5×5 Array{Float64,2}:\n",
       " 3.0   21.0           8.0       19.0       6.0    \n",
       " 0.0  -39.0          -2.33333  -17.6667    3.0    \n",
       " 0.0    0.0          -2.40672   -6.16534  -5.83002\n",
       " 0.0    0.0           0.0        0.0       1.0    \n",
       " 0.0    1.42109e-14  -5.4188   -48.0293    5.68005"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A3 = E2 * A2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element Array{Float64,1}:\n",
       " -0.0    \n",
       "  2.25153"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m3 = A3[4:5,3]/A3[3,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element Array{Float64,1}:\n",
       "  0.0    \n",
       " -2.25153"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E4 = eye(5)\n",
    "E4[4:5,3] = - m3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5×5 Array{Float64,2}:\n",
       " 3.0   21.0           8.0       19.0       6.0    \n",
       " 0.0  -39.0          -2.33333  -17.6667    3.0    \n",
       " 0.0    0.0          -2.40672   -6.16534  -5.83002\n",
       " 0.0    0.0           0.0        0.0       1.0    \n",
       " 0.0    1.42109e-14   0.0      -34.1479   18.8065 "
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A4 = E4 * A3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×5 Array{Float64,2}:\n",
       " 0.0  0.0  0.0  0.0  1.0\n",
       " 0.0  0.0  0.0  1.0  0.0"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P = eye(5)\n",
    "P[[4 5],:] = P[[5,4],:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5×5 Array{Float64,2}:\n",
       " 3.0   21.0           8.0       19.0       6.0    \n",
       " 0.0  -39.0          -2.33333  -17.6667    3.0    \n",
       " 0.0    0.0          -2.40672   -6.16534  -5.83002\n",
       " 0.0    1.42109e-14   0.0      -34.1479   18.8065 \n",
       " 0.0    0.0           0.0        0.0       1.0    "
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A4P = P * A4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5×5 Array{Float64,2}:\n",
       "  1.0       0.0  0.0  0.0  0.0\n",
       " -1.66667   1.0  0.0  0.0  0.0\n",
       " -0.745356  0.0  1.0  0.0  0.0\n",
       " -0.0       0.0  0.0  1.0  0.0\n",
       " -0.666667  0.0  0.0  0.0  1.0"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5×5 Array{Float64,2}:\n",
       " 1.0       0.0  0.0  0.0  0.0\n",
       " 1.66667   1.0  0.0  0.0  0.0\n",
       " 0.745356  0.0  1.0  0.0  0.0\n",
       " 0.0       0.0  0.0  1.0  0.0\n",
       " 0.666667  0.0  0.0  0.0  1.0"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inv(E1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Gaussian elimination: towards the wholistic view A=LU through elimination matrices\n",
    "\n",
    "Let's look more closely at the process of Gaussian elimination in matrix form, using the matrix from lecture 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       " 1   3   1\n",
       " 1   1  -1\n",
       " 3  11   6"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = [1 3  1\n",
    "     1 1 -1\n",
    "     3 11 6]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Gaussian elimination produces the matrix $U$, which we can compute in Julia as in lecture 1:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0   3.0   1.0\n",
       " 0.0  -2.0  -2.0\n",
       " 0.0   0.0   1.0"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# LU factorization (Gaussian elimination) of the matrix A, \n",
    "# passing the ( will go away) option Val{false} to prevent row re-ordering\n",
    "L, U = lu(A, Val{false}) \n",
    "U # just show U"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's go through **Gaussian elimination in matrix form**, by **expressing the elimination steps as matrix multiplications.**  In Gaussian elimination, we make linear combination of *rows* to cancel elements below the pivot, and we now know that this corresponds to multiplying on the *left* by some *elimination matrix* $E$.\n",
    "\n",
    "The first step is to eliminate in the first column of $A$.  The pivot is the 1 in the upper-left-hand corner.  For this $A$, we need to:\n",
    "\n",
    "1. Leave the first row alone.\n",
    "2. Subtract the first row from the second row to get the new second row.\n",
    "3. Subtract $3 \\times {}$ first frow from the third row to get the new third row.\n",
    "\n",
    "This corresponds to multiplying $A$ on the left by the matrix `E1`.  As above (in the \"row × matrix\" picture), the three rows of `E1` correspond exactly to the three row operations listed above:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       "  1  0  0\n",
       " -1  1  0\n",
       " -3  0  1"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E1 = [ 1 0 0\n",
    "      -1 1 0\n",
    "      -3 0 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       " 1  0  0\n",
       " 1  1  0\n",
       " 3  0  1"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Int.(inv(E1))  ## What does this mean?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       "  0.486247   0.762176   0.269746\n",
       " -0.325667  -0.127095  -0.254637\n",
       " -0.549413  -1.57389   -0.559246"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E1 * A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 0.486247  0.762176  0.269746 \n",
       " 0.160581  0.635081  0.0151095\n",
       " 0.909329  0.712643  0.249992 "
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inv(E1) *  (E1 * A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We would love for you to see the above not as a mechanical observation but interpret it as reversing the row operationa above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       " 1   3   1\n",
       " 0  -2  -2\n",
       " 0   2   3"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E1*A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As desired, this introduced zeros below the diagonal in the first column.  Now, we need to eliminate the 2 below the diagonal in the *second* column of `E1*A`.  Our new pivot is $-2$ (in the second row), and we just add the second row of `E1*A` with the third row to make the new third row.\n",
    "\n",
    "This corresponds to multiplying on the left by the matrix `E2`, which leaves the first two rows alone and makes the new third row by adding the second and third rows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       " 1  0  0\n",
       " 0  1  0\n",
       " 0  1  1"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E2 = [1 0 0\n",
    "      0 1 0\n",
    "      0 1 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       " 1   3   1\n",
       " 0  -2  -2\n",
       " 0   0   1"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E2*E1*A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected, this is upper triangular, and in fact the same as the `U` matrix returned by the Julia `lu` function above:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E2*E1*A == U"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thus, we have arrived at the formula:\n",
    "$$\n",
    "\\underbrace{E_2 E_1}_E A = U\n",
    "$$\n",
    "Notice that we multiplied $A$ by the elimination matrices from *right to left* in the order of the steps: it is $E_2 E_1 A$, *not* $E_1 E_2 A$.  Because matrix multiplication is generally [not commutative](https://en.wikipedia.org/wiki/Commutative_property), $E_2 E_1$ and $E_1 E_2$ give *different* matrices:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       "  1  0  0\n",
       " -1  1  0\n",
       " -4  1  1"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E2*E1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       "  1  0  0\n",
       " -1  1  0\n",
       " -3  1  1"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E1*E2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       "  1  0  0\n",
       " -1  1  0\n",
       " -3  0  1"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice, furthermore, that the matrices $E_1$ and $E_2$ are both *lower-[triangular](https://en.wikipedia.org/wiki/Triangular_matrix) matrices* with ones on the diagonal.  This is a consequence of the structure of Gaussian elimination (assuming no row re-ordering): we always add the pivot row to rows *below* it, never *above* it.\n",
    "\n",
    "The *product* of lower-triangular matrices is always lower-triangular too.  (In homework, you will explore a similar property for upper-triangular matrices)  In consequence, the product $E = E_2 E_1$ is lower-triangular, and Gaussian elimination can be viewed as yielding $EA=U$ where $E$ is lower triangular and $U$ is upper triangular.\n",
    "\n",
    "# Inverse elimination: LU factors\n",
    "\n",
    "We can write $EA=U$ as  $A= E^{-1} U$, where $E^{-1}$ is the [inverse of the matrix](http://mathworld.wolfram.com/MatrixInverse.html) $E$.  We will have more to say about matrix inverses later in 18.06, but for now we just need to know that it is the matrix that **reverses the steps** of Gaussian elimination, taking us back from $U$ to $A$.  Computing matrix inverses is laborious in general, but in this particular case it is easy.   We just need to *reverse the steps one by one* starting with the *last* elimination step and working back to the *first* one.  \n",
    "\n",
    "Hence, we need to reverse (invert) $E_2$ *first* on $U$, and *then* reverse (invert) $E_1$: $A = E_1^{-1} E_2^{-1} U$.  But reversing an individual elimination step like $E_2$ is easy: we just **flip the signs below the diagonal**, so that wherever we *added* the pivot row we *subtract* and vice-versa.  That is:\n",
    "$$\n",
    "\\begin{pmatrix} 1 & 0 & 0 \\\\ 0 & 1 & 0 \\\\ 0 & 1 & 1 \\end{pmatrix}^{-1} =\n",
    "\\begin{pmatrix} 1 & 0 & 0 \\\\ 0 & 1 & 0 \\\\ 0 & -1 & 1 \\end{pmatrix}\n",
    "$$\n",
    "(The last elimination step was adding the second row to the third row, so we reverse it by *subtracting* the second row from the third row of $U$.)\n",
    "\n",
    "Julia can compute matrix inverses for us with the `inv` function.  (It doesn't know the trick of flipping the sign, which only works for very special matrices, but it can compute it the \"hard way\" so quickly (for such a small matrix) that it doesn't matter.)   Of course that gives the same result:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0   0.0  0.0\n",
       " 0.0   1.0  0.0\n",
       " 0.0  -1.0  1.0"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inv(E2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly for $E_1$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0  0.0  0.0\n",
       " 1.0  1.0  0.0\n",
       " 3.0  0.0  1.0"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inv(E1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we didn't make any mistakes, then $E_1^{-1} E_2^{-1} U$ should give $A$, and it does:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inv(E1)*inv(E2)*U == A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use the letter \"L\" for the *inverse* elimination matrix $L = E^{-1} = E_1^{-1} E_2^{-1}$  Since the inverses of each elimination matrix were lower-triangular (with flipped signs), their product $L$ is also lower triangular:\n",
    "\n",
    "(Think of a mechanical reason that products of lower-triangular are lower-triangular and a conceptual reason.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0   0.0  0.0\n",
       " 1.0   1.0  0.0\n",
       " 3.0  -1.0  1.0"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L = inv(E1)*inv(E2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As mentioned above, this is the same as the inverse of $E = E_2 E_1$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0   0.0  0.0\n",
       " 1.0   1.0  0.0\n",
       " 3.0  -1.0  1.0"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inv(E2*E1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The final result, therefore, is that Gaussian elimination (without row swaps) can be viewed as a *factorization* of the original matrix $A$\n",
    "$$\n",
    "A = LU\n",
    "$$\n",
    "into a **product of lower- and upper-triangular matrices**.  (Furthermore, although we didn't comment on this above, $L$ is always 1 along its diagonal.)  This factorization is called the [LU factorization](https://en.wikipedia.org/wiki/LU_decomposition) of $A$.  (It's why we used the `lu` function in Julia above.)  When a computer performs Gaussian elimination, what it computes are the $L$ and $U$ factors.\n",
    "\n",
    "What this accomplishes is to break a complicated matrix $A$ into **much simpler pieces** $L$ and $U$.  It may not seem at first that $L$ and $U$ are *that* much simpler than $A$, but they are: lots of operations that are very difficult with $A$, like solving equations or computing the determinant, become *easy* once you known $L$ and $U$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0   0.0  0.0\n",
       " 1.0   1.0  0.0\n",
       " 3.0  -1.0  1.0"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0   0.0  0.0\n",
       " 1.0   1.0  0.0\n",
       " 3.0  -1.0  1.0"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inv(E2*E1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       "  1  0  0\n",
       " -1  1  0\n",
       " -3  0  1"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       " 1  0  0\n",
       " 0  1  0\n",
       " 0  1  1"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "E1 and E2 have the negative multipliers below the diagonal\n",
    "\n",
    "inv(E1) and inv(E2) have the multipliers below\n",
    "the diagonal.\n",
    "\n",
    "L has the multipliers below the diagonal.\n",
    "\n",
    "inv(L) does not generally have multipliers anywhere."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0   0.0  0.0\n",
       " 1.0   1.0  0.0\n",
       " 3.0  -1.0  1.0"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       "  1.0  0.0  0.0\n",
       " -1.0  1.0  0.0\n",
       " -4.0  1.0  1.0"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inv(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       "  1  0  0\n",
       " -1  1  0\n",
       " -3  0  1"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0  0.0  0.0\n",
       " 1.0  1.0  0.0\n",
       " 3.0  0.0  1.0"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inv(E1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       " 1  0  0\n",
       " 0  1  0\n",
       " 0  1  1"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0   0.0  0.0\n",
       " 0.0   1.0  0.0\n",
       " 0.0  -1.0  1.0"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inv(E2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0   0.0  0.0\n",
       " 1.0   1.0  0.0\n",
       " 3.0  -1.0  1.0"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       "  1.0  0.0  0.0\n",
       " -1.0  1.0  0.0\n",
       " -4.0  1.0  1.0"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inv(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       "  1  0  0\n",
       " -1  1  0\n",
       " -3  0  1"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E1 # differs from I in column 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       " 1  0  0\n",
       " 0  1  0\n",
       " 0  1  1"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E2 # differs from I in column 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       " 1.0   0.0  0.0\n",
       " 1.0   1.0  0.0\n",
       " 3.0  -1.0  1.0"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L# differs from I in more than one column L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Int64,2}:\n",
       "  1  0  0\n",
       " -1  1  0\n",
       " -4  1  1"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E2 * E1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.6.0",
   "language": "julia",
   "name": "julia-0.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
